package com.剑指offer.第七章队列;

import java.util.LinkedList;
import java.util.Queue;

public class CBTInsert {

    private Queue<TreeNode> queue;

    private TreeNode node;

    public CBTInsert(TreeNode root) {
        this.node = root;
        this.queue = new LinkedList<>();


        this.queue.offer(root);

        // 用队列 做广度优先
        /**
         * 当一个节点的左右子节点，都存在，则将该节点移出队列中
         */
        while (this.queue.peek().left != null && this.queue.peek().right != null) {
            TreeNode poll = this.queue.poll();

            this.queue.offer(poll.left);

            this.queue.offer(poll.right);

        }

    }

    public void insert(int val) {
        TreeNode peek = this.queue.peek();

        TreeNode treeNode = new TreeNode();
        treeNode.val = val;

        if (peek.left != null) {
            peek.left = treeNode;
        } else {
            peek.right = treeNode;
            this.queue.poll();
            this.queue.offer(peek.left);
            this.queue.offer(peek.right);
        }
    }


    public TreeNode getRoot() {
        return this.node;
    }

}
